class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
       List<Integer> list = new ArrayList<>() ;
       if(root == null) return list ;
       Stack<TreeNode> stack1 = new Stack<>() ;
       Stack<TreeNode> stack2 = new Stack<>() ;
      stack1.push(root);
      while(!stack1.empty() || !stack2.empty()){
        if(!stack1.empty()){
            TreeNode cur = stack1.pop() ;
            if(cur.left!=null || cur.right!=null){
                 stack2.push(cur);
                 if(cur.left != null){
                    stack1.push(cur.left);
                 }
            }else{
              list.add(cur.val);
            }
        }else{
            TreeNode cur = stack2.pop() ;
            list.add(cur.val);
            if(cur.right != null){
                stack1.push(cur.right);
            }
        }
      }

        return list ;
       
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null)return list ;
        Stack<TreeNode> stack = new Stack<>() ;
        stack.push(root);
        while(!stack.empty()){
            TreeNode cur = stack.pop() ;
            list.add(cur.val);
            if(cur.right != null){
                stack.push(cur.right);
            }
            if(cur.left != null){
                stack.push(cur.left);
            }
        }
        return list ;
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>() ;
        if(root == null) return list ;
        Stack<TreeNode> stak = new Stack<>() ;
        TreeNode cur = root ;
        TreeNode top = null ;
        TreeNode prve = null ;
        while(cur!=null || !stak.empty()){
            while(cur != null){
                stak.push(cur);
                cur = cur.left ;
            }
            top = stak.peek() ;
            if(top.right == null || top.right == prve){
                list.add(top.val);
                stak.pop() ;
                prve = top ;
            }else{
                cur = top.right ;
            }
        }


        return list ;

    }
}